// https://leetcode.cn/problems/linked-list-cycle-ii/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 快慢指针法检测链表环的入口节点
// 2. 第一阶段：找到快慢指针相遇点
// 3. 第二阶段：从头和相遇点同时出发，相遇处即为环入口
// 4. 数学原理：头节点到环入口距离 = 相遇点到环入口距离
// 5. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>
#include "LinkedListUtils.h"

class Solution 
{
public:
    ListNode* detectCycle(ListNode* head) 
    {
        ListNode* slow = head, *fast = head;

        while (fast != nullptr && fast->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next->next;

            if (slow == fast)
            {
                ListNode* meet = slow;
                while (head != meet)
                {
                    head = head->next;
                    meet = meet->next;
                }

                return meet;
            }
        }

        return nullptr;
    }
};

int main()
{
    vector<int> nums1 = {3,2,0,-4}, nums2 = {1,2};
    Solution sol;

    auto l1 = createLinkedList(nums1);
    l1->next->next->next->next = l1->next;

    auto l2 = createLinkedList(nums2);
    l2->next->next = l2;

    cout << (sol.detectCycle(l1)->val) << endl;
    cout << (sol.detectCycle(l2)->val) << endl;

    return 0;
}